λ¬Έμ
Programmers - λΆλ μ¬μ©μ
π Logic
public void findBadUser(HashSet<String> set, int size) {
if (size == bannedIdList.size()) {
banSet.add(new HashSet<>(set));
return;
}
// listλ²μ§Έ μ μ¬ μμ΄λλ₯Ό setμ μΆκ°
for (String id : bannedIdList.get(size)) {
if (set.contains(id)) continue;
set.add(id);
findBadUser(set, size + 1);
set.remove(id);
}
}
- DFS λ°©μμΌλ‘ μ μ¬ μμ΄λ
setμ μμ±νκ³ , μ΄λ₯Ό μ€λ³΅μ΄ μλλ‘ νκΈ° μν΄HashSetμ μ μ₯νλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
import java.util.regex.Pattern;
class Ban {
HashSet<HashSet<String>> banSet;
ArrayList<ArrayList<String>> bannedIdList;
public Ban() {
banSet = new HashSet<>();
bannedIdList = new ArrayList<>();
}
public void makeSet(String banned_id, String[] user_id) {
// μ κ·ννμ μ¬μ©μ μν΄ λ³ν
String regex = banned_id.replace('*', '.');
ArrayList<String> tmpList = new ArrayList<>();
for (String user : user_id) {
boolean isMatch = Pattern.matches(regex, user);
if (isMatch) tmpList.add(user);
}
bannedIdList.add(tmpList);
}
public void findBadUser(HashSet<String> set, int size) {
if (size == bannedIdList.size()) {
banSet.add(new HashSet<>(set));
return;
}
// listλ²μ§Έ μ μ¬ μμ΄λλ₯Ό setμ μΆκ°
for (String id : bannedIdList.get(size)) {
if (set.contains(id)) continue;
set.add(id);
findBadUser(set, size + 1);
set.remove(id);
}
}
public int getCount() {
return banSet.size();
}
}
class Solution {
public int solution(String[] user_id, String[] banned_id) {
Ban b = new Ban();
for (String ban : banned_id)
b.makeSet(ban, user_id);
b.findBadUser(new HashSet<>(), 0);
return b.getCount();
}
}
βοΈ Review
- μ κ· ννμλ§μΌλ‘ ν΄κ²°νλ €κ³ νμ§λ§, DFS λ°©μμΌλ‘ μ€λ³΅μ νμΈνλ κ³Όμ μ΄ νμνλ€.
- μ΄λ° μ νμ DFS, BFS λ°©μμ λ¬Έμ λ μμ μ μλ€λ κ²μ μκ² λμλ€.